Tech Arsenal 1/Tech Arsenal (Arsenal Computer).ISO/tek-13/emac16ds.zip/MINTFORM.ASM

Assembly Source File | 1991-08-03 | 15KB | 537 lines

title    minform.asm: MINT string data structure manipulator.
;History:14,1
;Mon May 06 00:58:06 1991 experiment with sgap marker.
;Tue May 22 10:27:09 1990 skip readjustments when deleting last form
;Sat May 19 21:16:53 1990 Change available space computation in define_form
;Tue Sep 12 23:49:09 1989 Add the find_string entry point.
;10-01-88 14:45:52 make get_mint_space return four numbers.
;12-06-87 00:51:14 finish adding 256K of mint space.
;12-06-87 00:26:46 start adding support for 256K of mint space.
;11-16-87 23:18:00 call new_buffer from init_forms.
    page    ,132

    .xlist
    include emacs.def
    include    mintform.def
    include    mint.def
    .list

comment \

The forms:

    Forms are laid out as a linear list of forms.  formStore points to the
beginning, and [topbot] points to the end.  The most recently defined forms are
placed at the beginning of the list.  The forms consists of three elements: a
header, the name, and the data.  The header contains the link to the next
form, the length of the name, the length of the data, and the form pointer
(which is always <= the length of the data).  The form structure is defined in
the file 'mintform.def'.
    When a form is to be looked up in form storage, the form is first
hashed.  Then the form is looked up in the list of hash links.  A linear search
is performed for all the forms that hash to that value.

    formhash is the hashing table for form names.  It is a list of
pointers to forms.  Each form, in turn, has a pointer to the next form
whose name hashes to the same entry in formhash. To add a new form, we
must add the name to the proper place in the table.  To delete a form, the
form name must be removed from formhash.  Their links in formhash and each
of the forms must be updated, then the remaining forms get moved up in
memory.

    Also, whenever a form gets looked up, it is placed at the head of
the chain of hash pointers.  The assumption is that it will be looked up
again shortly.

From: zardoz!sivs![e-mail] (Hugh Daschbach)

Russ,

Thanks again for freemacs.  I find it invaluable.  I thought you
might be interested in the following.  I pass it along for your
information and review.

I recently wondered where all the time is spent in the next-buffer
and previous-buffer services.  I rigged up a quick and dirty profiler
and found that roughly 20% of the time, the program was executing
code in delete_form.  This surprised me.  I considered modifying the
form allocation and deallocation routines to see if I could reduce
the overhead of deleting forms.  Before doing this, however, I found
two simple modifications reduced this overhead.

The first is a change to find_form.  I noticed that find_form
used form_struc.data_length instead of form_struc.form_length to
determine if there is enough space to redefine an existing form.
Using form_length (adjusted by name_length and size form_struc)
reduced CPU utilization of delete_form from 20% to 5% in
next-buffer/previous-buffer operations.

For the second change, I skip the hash table and form buffer space
adjustments if the form being deleted is the last form in the buffer.
This reduce to CPU utilization of delete_form from 5% to 3% of
next-buffer/previous-buffer operations.

The following are diffs of mintform.asm based on the 1.6a sources.
I specifically disclaim ownership of these changes.  You can do anything
you want with them.

[ Diffs installed && deleted ]

Just in case you are interested this is the profiler's report of
CPU utilization of routines executing during a next-buffer or
previous-buffer request after implementing these two modifications:

  20% GS_PRIM
  16% DOS
  13% LS_PRIM
  10% BUFFER_CHECK
   7% NEXT_FORM
   6% SCAN_RPAR_SUB
   3% DELETE_FORM
   3% FIND_STRING
   3% RETURN_ACTIVE
   3% GETARG
   2% FIND_FORM
   1% TRACE_RESULT
   0% TRACE_INVOKE

\


formSeg    segment    byte public

    define_buffer    form_

    public    syntax_table
syntax_table    dw    NIL
;don't put anything here.
formhashsize    equ    256
formhash    dw formhashsize dup(NIL)

formStore    label    byte


formSeg    ends


segmoffs    struc
offs        dw    ?
segm        dw    ?
segmoffs    ends


data    segment byte public

    public    syntax_seg
syntax_seg    dw    formSeg        ;segment holding syntax table.

this_segment    dw    ?        ;points to next formSegments to get.
this_form    dd    ?        ;current form while enumerating.

    public    formSeg0, formSeg1, formSeg2, formSeg3
formSegments    label    word
formSeg0    dw    ?
formSeg1    dw    ?
formSeg2    dw    ?
formSeg3    dw    ?

    extrn    data_bottop: word

data    ends


code    segment byte public

    assume cs:code

    extrn    buffer_free: near
    extrn    new_buffer: near
    extrn    put_number: near

    public    init_forms
init_forms:
    mov    cx,4
    mov    bx,offset formSegments
init_forms_0:
    assume    ds:data, es:data
    push    bx
    push    cx
    mov    cx,offset formStore
    call    new_buffer
    pop    cx
    pop    bx
    jc    init_forms_1
    xchgdses
    assume    ds:data, es:formSeg
    mov    [bx],es                ;remember this form segment.
    add    bx,2
    push    cx
    mov    di,offset syntax_table        ;null out the hash table.
    xor    ax,ax
    mov    cx,256 + 1
    rep    stosw
    mov    ax,offset formStore        ;->end of forms.
    mov    form_topbot,ax
    mov    form_bottop,ax
    mov    form_botbot,ax
    esdata
    pop    cx
    loop    init_forms_0
    clc
init_forms_1:
    ret


    public    get_mint_space
get_mint_space:
;enter with di -> place to put numbers.
;return four numbers giving the bytes of mint space available,
;  di ->end of strings.
    mov    dx,ds            ;start with ds.
    mov    cx,4            ;do four segments.
get_mint_space_1:
    push    ds            ;get the next segment
    mov    ds,dx
    assume    ds:formseg
    mov    dx,form_next_buffer
    mov    ds,dx
    mov    ax,form_bottop        ;get the free space for this buffer.
    sub    ax,form_topbot
    pop    ds
    assume    ds:data

    push    dx
    push    cx
    mov    cx,0            ;use only as many digits as is needed.
    mov    bx,10
    call    put_number
    mov    al,','            ;seperate them by commas.
    stosb
    pop    cx
    pop    dx
    loop    get_mint_space_1
    ret


;first_form sets us up to enumerate the forms (in no particular order).
;  Returns es:bx ->next form, zr if there is no next form.  Do not assume
;  that es will remain the same from one call to the next.
    public    first_form, next_form
first_form:
    assume    ds:data, es:data
    mov    this_segment,offset formSegments
next_segment:
    assume    ds:data, es:nothing
    mov    bx,this_segment
    add    this_segment,2            ;postincrement to the next seg.
    cmp    bx,offset formSegments + 4*2    ;last form segment?
    jz    next_last            ;yes - we're done.
    mov    ax,[bx]                ;get the formSegment.
    mov    this_form.segm,ax
    mov    this_form.offs,offset formStore    ;->beginning of forms.
next_form:
    les    bx,this_form
    assume    es:formSeg
    mov    ax,formSeg:[bx].form_length    ;postincrement to the next form.
    add    this_form.offs,ax
    cmp    bx,form_topbot            ;go if we have no more forms.
    je    next_segment
next_last:
    ret


;enter with ds:bx -> a form.  Make that form be the syntax table.

    public    store_syntax_table
store_syntax_table:
    assume    ds:formSeg, es:data
    mov    syntax_table,bx
    mov    syntax_seg,ds
    ret


;define a form.  Enter with:
;    si => name
;    cx = name length
;    di => data
;    dx = data length
;    bx = form pointer.

    public    define_form
define_form:
    assume    ds:data, es:data
    push    bx            ;save the form pointer.
    call    find_form        ;see if it already exists.
    jc    define_form_1        ;it doesn't.
    assume    es:formSeg
;check to see if the form is already big enough.
    mov    bp,dx
    and    bp,7fffh        ;get rid of the sgap marker.
    mov    ax,formSeg:[bx].form_length
    sub    ax,cx
    sub    ax,(size form_struc)
    cmp    ax,bp
    jbe    define_form_3            ;it isn't.
    pop    formSeg:[bx].form_pointer        ;set the form pointer.
    mov    si,di                ;prepare to move the data.
    lea    di,formSeg:[bx].name_offset    ;->name.
    add    di,cx                ;->data.
    mov    formSeg:[bx].data_length,dx    ;set the data length.
    mov    cx,bp                ;copy the new data in.
    movmem
    esdata
    ret
define_form_3:
    assume    es:formSeg
    push    di            ;delete the form pointed to by es:bx
    push    si
    push    cx
    call    delete_form
    pop    cx
    pop    si
    pop    di
    esdata
define_form_1:
    pop    bx        ;restore form pointer.
    push    di
    push    bx
    push    si
    push    cx
    call    hash_func        ;exit with es:[bx]->hash entry.
    assume    es:formSeg
    mov    bp,dx
    and    bp,7fffh        ;get rid of the sgap marker.
    add    cx,(size form_struc)    ;compute amount of space needed.
    add    cx,bp
    push    cx            ;push the size
    mov    ax,es
    call    buffer_free
    jc    define_form_2            ;go if we can't get enough mem.
    mov    di,form_topbot
    pop    formSeg:[di].form_length        ;get the total size. (pushed as cx)
    pop    cx                ;we have to pop into cx, because we
    mov    formSeg:[di].name_length,cx    ;  need it later for the movsb.
    mov    formSeg:[di].data_length,dx
    pop    si                ;restore ->name
    pop    formSeg:[di].form_pointer
    mov    ax,formSeg:[bx]            ;get current formhash
    mov    formSeg:[bx],di            ;make formhash point to us.
    mov    formSeg:[di].hash_link,ax        ;make us point to current formhash.
    add    di,name_offset            ;lea    di,[di].name_offset
    movmem
    pop    si                ;restore ->data
    mov    cx,bp
    movmem
    mov    form_topbot,di            ;remember the new end.
    esdata
    ret
define_form_2:
    call    nomem


;Find a form.  Enter with:
;    si -> name
;    cx = name length
;Preserve di
;Exit with:
;    nc if form found, es:bx -> form
;    cy if form not found, es=data
    public    find_form
find_form:
    assume    ds:data, es:data
    push    dx
    push    di
    call    hash_func
    assume    es:formSeg
    push    bx            ;remember the formhash pointer.
    xor    dx,dx
    mov    bx,formSeg:[bx]        ;get ->first form that hashes here.
find_form_1:
    cmp    bx,NIL                ;end of list?
    je    find_form_2            ;yes, we didn't find it.
    cmp    cx,formSeg:[bx].name_length    ;lengths equal?
    jne    find_form_3            ;no, go to next.
    lea    di,formSeg:[bx].name_offset    ;compare names.
    push    si
    push    cx
    rep    cmpsb
    pop    cx
    pop    si
    jne    find_form_3        ;names not equal.
    pop    di            ;restore the formhash pointer.
    or    dx,dx            ;did we find it first?
    je    find_form_4        ;yes - that's where we want it.
    mov    ax,formSeg:[di]
    mov    formSeg:[di],bx        ;make head -> found.
    xchg    ax,formSeg:[bx].hash_link    ;make found -> old head.
    mov    di,dx
    mov    formSeg:[di].hash_link,ax    ;make pred(found) -> succ(found).
find_form_4:
    clc                ;found the form!
    pop    di
    pop    dx
    ret
find_form_3:
    assume    es:formSeg
    mov    dx,bx
    mov    bx,formSeg:[bx].hash_link
    jmp    find_form_1
find_form_2:
    pop    bx        ;restore the formhash pointer.
    esdata
    stc            ;didn't find the form!
    pop    di
    pop    dx
    ret


;delete a form.  Enter with:
;    es:bx=>form

    public    delete_form
delete_form:
;delete the form from the hashing table.
    assume    ds:data, es:formSeg
    mov    di,bx            ;make a copy of the pointer to the form.
    mov    cx,formSeg:[bx].name_length
    lea    si,formSeg:[bx].name_offset
    xchgdses
    assume    ds:formSeg, es:data
    call    hash_func
    assume    es:formSeg
    sub    bx,hash_link        ;pretend that formhash is a form itself.
delete_form_1:
    cmp    formSeg:[bx].hash_link,di    ;does this form point to us?
    je    delete_form_2        ;yes.
    mov    bx,formSeg:[bx].hash_link    ;no - go to the next form.
    jmp    delete_form_1
delete_form_2:
    mov    ax,formSeg:[di].hash_link    ;unlink us from the list.
    mov    formSeg:[bx].hash_link,ax
;check for deletion of the syntax table.
    cmp    di,syntax_table
    jne    delete_form_7
    mov    syntax_table,NIL    ;if we're deleting it, put NIL in.
delete_form_7:
    mov    ax,di            ;if last form, skip readjustments
    add    ax,formSeg:[di].form_length
    cmp    ax,form_topbot
    je    delete_form_8
;now adjust the hash links in formhash.
    mov    ax,formSeg:[di].form_length
    mov    bx,offset syntax_table
    mov    cx,formhashsize+1    ;add one for the syntax table.
delete_form_3:
    cmp    formSeg:[bx],di        ;do we need to adjust this one?
    jbe    delete_form_4        ;no.
    sub    formSeg:[bx],ax        ;yes - do it.
delete_form_4:
    add    bx,2
    loop    delete_form_3
;now adjust all the hash links in the forms.  Notice that we are adjusting
;  the hash link in the form we are about to delete, but it doesn't hurt.
;  We can also presume the existence of at least one form at this point.
    mov    bx,offset formStore        ;->beginning of forms.
delete_form_5:
    cmp    formSeg:[bx].hash_link,di    ;do we need to adjust this one?
    jbe    delete_form_6        ;no.
    sub    formSeg:[bx].hash_link,ax    ;yes - do it.
delete_form_6:
    add    bx,formSeg:[bx].form_length    ;compute the form after this one.
    cmp    bx,form_topbot            ;no forms after this one.
    jb    delete_form_5
    mov    si,di            ;now move every form after this one down.
    add    si,ax
    mov    cx,form_topbot
    sub    cx,si
    movmem
delete_form_8:
    mov    form_topbot,di        ;remember the new form_topbot.
    dsdata
    esdata
    ret


;find the form whose name is given in arg1.  Return the form pointer in
;ds:si, and the number of bytes remaining in the form in cx.
    public    find_arg1
find_arg1:
    mov    cx,1
;fall through to find_arg

;find the form whose name is given in the argument specified in cx.  Return
;  the form pointer in ds:si, and the number of bytes remaining in the form in
;  cx, and the pointer to the form in bx.
    public    find_arg
find_arg:
    assume    ds:data, es:data
    call    getarg
    public    find_string
find_string:
    call    find_form
    jc    find_arg1_1            ;if form doesn't exist, exit.
    xchgdses
    assume    ds:formSeg, es:data
    lea    si,formSeg:[bx].name_offset    ;make si => form.data
    add    si,formSeg:[bx].name_length
    add    si,formSeg:[bx].form_pointer
    mov    cx,formSeg:[bx].data_length    ;make cx = number of bytes left.
    and    cx,7fffh            ;get rid of sgap marker.
    sub    cx,formSeg:[bx].form_pointer
    clc                    ;remember that form was found.
find_arg1_1:
    ret


hash_func:
;enter with si,cx ->name to be hashed.
;exit with entry into hash table in ds:bx
;preserve dl.
    assume    ds:nothing
    push    si
    push    cx
    xor    bx,bx            ;start with zero.
    jcxz    hash_func_1
    xor    ah,ah
hash_func_2:
    lodsb
    add    bx,ax
    loop    hash_func_2
hash_func_1:
    mov    al,bl            ;save the low byte
    mov    bl,bh
    mov    bh,0
    and    bl,3            ;four segments = two bits.
    add    bx,bx            ;we're accessing words.
    mov    es,formSegments[bx]    ;get the correct segment.
    mov    bl,al            ;get the low byte back.  No need to
                    ;zero bh again.
    add    bx,bx
    add    bx,offset formhash
    pop    cx
    pop    si
    ret


;Adjust the form pointer after building a value which affects the
;  form pointer.  The new form pointer is derived from the count
;  of characters left in cx.  The form is pointed to by bx.
    public    return_form
return_form:
    assume    ds:formSeg, es:data
    mov    ax,formSeg:[bx].data_length
    and    ax,7fffh        ;remove sgap marker.
    sub    ax,cx
    mov    formSeg:[bx].form_pointer,ax
    dsdata
    jmp    return_tos


    extrn    return_tos: near
    extrn    getarg: near
    extrn    nomem: near
code    ends

    end